package com.zjsru.leetcode75.level1.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: cookLee
 * @Date: 2023-12-11
 * 二叉树的右视图
 */
public class RightSideView {

    /**
     * 主
     * \
     * 输入: [1,2,3,null,5,null,4]
     * 输出: [1,3,4]
     * \
     * 输入: [1,null,3]
     * 输出: [1,3]
     * \
     * @param args args
     */
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(1, new TreeNode(2, null, new TreeNode(5, null, null)), new TreeNode(3, null, new TreeNode(4, null, null)));
        RightSideView rightSideView = new RightSideView();
        System.out.println(rightSideView.rightSideView(tree));
    }

    List<Integer> ans = new ArrayList<>();

    /**
     * 级别
     */
    int deep = 0;

    /**
     * 右侧视图：层级遍历
     *
     * @param root 根
     * @return {@link List}<{@link Integer}>
     */
    public List<Integer> rightSideView(TreeNode root) {
        this.dfs(root,0);
        return ans;
    }

    /**
     * dfs
     * 助手类
     *
     * @param root  根
     * @param level 级别
     */
    private void dfs(TreeNode root, int level) {
        if (root == null) {
            return;
        }
        //检查当前节点是否为当前级别的最右侧节点,level > deep处理是否进入下一层,比如左子树比右子树长的时候
        if (level == deep && ans.size() == deep || level > deep) {
            ans.add(root.val);
            deep++;
        }
        //位置不能替换,优先处理左侧节点
        this.dfs(root.right, level + 1);
        this.dfs(root.left, level + 1);
    }
}
